package com.lw.leetcode.dp.b;

import java.util.ArrayList;
import java.util.List;

/**
 * dp
 * 面试题 08.14. 布尔运算
 *
 * @Author liw
 * @Date 2021/8/28 18:35
 * @Version 1.0
 */
public class CountEval {

    public static void main(String[] args) {
        CountEval test = new CountEval();

        // 2
//        String str = "1^0|0|1";
//        int n = 0;

        // 10
//        String str = "0&0&0&1^1|0";
//        int n = 1;

        // 3840248
        String str = "0^1^0|0^0|0|1&0&1|0&1|1&1|1&0^0";
        int n = 0;
        long l = System.currentTimeMillis();
        int list = test.countEval(str, n);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(list);

    }

    public int countEval(String expression, int result) {
        char[] chars = expression.toCharArray();
        List<Integer> valueList = new ArrayList<>();
        List<Character> opList = new ArrayList<>();
        for (char c : chars) {
            if (c == '|' || c == '&' || c == '^') {
                opList.add(c);
            } else {
                valueList.add(c - 48);
            }
        }
        int length = valueList.size();
        long[][] arr = new long[length][length];
        for (int i = 0; i < length; i++) {
            if (valueList.get(i) == 1) {
                arr[i][i] = 1L << 32;
            } else {
                arr[i][i] = 1L;
            }
        }

        long item = 0XFFFFFFFFL;
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                long c1 = 0L;
                long c0 = 0L;
                for (int k = i; k < j; k++) {
                    long a = arr[i][k];
                    long b = arr[k + 1][j];
                    long a1 = a >> 32;
                    long a0 = a & item;
                    long b1 = b >> 32;
                    long b0 = b & item;
                    char ch = opList.get(k);
                    if (ch == '|') {
                        c1 += a1 * (b1 + b0) + a0 * b1;
                        c0 += b0 * a0;
                    } else if (ch == '&') {
                        c1 += a1 * b1;
                        c0 += a0 * (b1 + b0) + a1 * b0;
                    } else {
                        c1 += a1 * b0 + a0 * b1;
                        c0 += a0 * b0 + a1 * b1;
                    }
                }
                arr[i][j] = (c1 << 32) + c0;
            }
        }
        long aLong = arr[0][length - 1];
        if (result == 0) {
            return (int) (aLong & item);
        } else {
            return (int) (aLong >> 32);
        }
    }


}
